#include<iostream>

#include<vector>;
using namespace std;






vector<vector<int>> ret;
vector<int> path;

void dfs(int pos, int k, int n)
{
    if (path.size() == k)
    {
        ret.push_back(path);
        return;
    }

    for (int i = pos; i <= n; i++)
    {
        path.push_back(i);
        dfs(pos + 1, k, n);
        path.pop_back();
    }

}
vector<vector<int>> combine(int n, int k) {
    dfs(1, k, n);
    return ret;
}

int main()
{
    combine(4, 2);

    return 0;
}

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> combine(int n, int k) {
        dfs(1, k, n);
        return ret;
    }

    void dfs(int pos, int k, int n)
    {
        if (path.size() == k)
        {
            ret.push_back(path);
            return;
        }

        for (int i = pos; i <= n; i++)
        {
            path.push_back(i);
            dfs(i + 1, k, n);
            path.pop_back();
        }

    }
};